using System;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0968. 监控二叉树")]
    public class No0968_MinCameraCover : AbsBaseTestItem
    {
        /*
        给定一个二叉树，我们在树的节点上安装摄像头。
        节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
        计算监控树的所有节点所需的最小摄像头数量。

        提示：
            给定树的节点数的范围是 [1, 1000]。
            每个节点的值都是 0。
        */

        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }

        public override void OnTest()
        {
            Assert.TestExe(MinCameraCover,
                new TreeNode(1)
                {
                    left = new TreeNode(1)
                    {
                        left = new TreeNode(1) { },
                        right = new TreeNode(1) { },
                    },
                }, 1);

            Assert.TestExe(MinCameraCover,
                new TreeNode(1)
                {
                    left = new TreeNode(1)
                    {
                        left = new TreeNode(1)
                        {
                            left = new TreeNode(1)
                            {
                                left = new TreeNode(1),
                            },
                        },
                    },
                }, 2);
        }

        public int MinCameraCover(TreeNode root)
        {
            int[] dfs(TreeNode root)
            {
                if (root == null)
                {
                    return new int[] { int.MaxValue / 2, 0, 0 };
                }
                int[] leftArray = dfs(root.left);
                int[] rightArray = dfs(root.right);
                int[] array = new int[3];
                array[0] = leftArray[2] + rightArray[2] + 1;
                array[1] = Math.Min(array[0], Math.Min(leftArray[0] + rightArray[1], rightArray[0] + leftArray[1]));
                array[2] = Math.Min(array[0], leftArray[1] + rightArray[1]);
                return array;
            }
            int[] array = dfs(root);
            return array[1];
        }
    }
}
